Minichallenge SAN - HS24

Das Soziale Netzwerk schlägt zurück

Von Haris Alic, Lukas Zemp und Kevin Wartmann

Imports

# imports
import json
import networkx as nx
from networkx.algorithms.community import louvain_communities
import matplotlib.pyplot as plt
import pandas as pd
import seaborn as sns
import plots
import importlib
from utils import load_json

1 Datensatz und Ausgangslage

1.1 Datensatz

Der Datensatz, den wir für unsere Challenge verwendet haben, ist der "Star Wars Social Network" Datensatz von Kaggle. Er umfasst insgesamt 25 JSON-Dateien, von denen jedoch nicht alle für unsere Analyse verwendet wurden. Die Datensätze sind nach den Star-Wars-Episoden I bis VII gegliedert, enthalten aber auch Zusammenfassungen sämtlicher Charaktere über mehrere Filme hinweg. Dabei finden sich Informationen zu den Figuren.

Besonders interessant sind die „mentions“- und „interactions“-Dateien, in denen die Häufigkeit von Erwähnungen (mentions) und den Interaktionen (interactions) zwischen Charakteren aufgeführt ist. Diese Angaben erlauben es, ein Netzwerk aus den Beziehungen der Figuren zu konstruieren und die Kantenstärken (Gewichtungen) zu quantifizieren. Anhand dieser Daten lassen sich beispielsweise zentrale Figuren und eng miteinander verbundene Gruppen identifizieren oder verschiedene Netzwerk- und Community-Erkennungsverfahren anwenden.

Der Datensatz ist auf Kaggle frei zugänglich: https://www.kaggle.com/datasets/ruchi798/star-wars

1.2 Ausgangslage

Im Universum ist Unruhe ausgebrochen. Der Imperator ist dabei Fehlinformationen zu verbreiten um seine macht in der Galaxie noch weiter ausbauen zu können. Die Bewohner der verschiedenen Sonnensysteme können die Wahrheit nicht mehr von Lügen unterscheiden. Um seinen dunklen Plan durchsetzen zu können, ist der Imperator dabei seine Desinformationen in alle Winkel der Galaxis zu verstreuen. Nur ein kleines Team von Data Scientists auf dem Planeten Erde ist dabei, sich dem Imperator entgegenzustellen. Mit hilfe von verschiedenen Methoden aus der Sozialen Netzwerkanalyse, möchten sie die Pläne des Imperators kreuzen. Allerdings hat auch der Imperator die Macht der Sozialen Netzwerkanalyse erkannt und nutz diese für seine Pläne. Welche Seite die Analyse Möglichkeiten besser nutzen kann und am Ende den Sieg erzielt, liegt noch in den Sternen.

1.3 Theorie verweis

Als Grundquelle für alle Theroie Abschnitte in diesem Notbebook gilt das SNA Skript 3.8 vom Juli 2024. Das Skript findet man unter folgendem Link:

https://spaces.technik.fhnw.ch/lernmaterialien/file/san-skript-v381-november-2024

2 Explorative Datenanalyse

Für die verwendeten Datensätze sind hier eine kleine Analyse

2.1 Alle Charakter mention und interaction

full_interaction_data = load_json("data/starwars-full-interactions-allCharacters.json")
full_mention_data = load_json("data/starwars-full-mentions.json")

int_nodes = full_interaction_data.get("nodes", [])
int_links = full_interaction_data.get("links", [])
ment_nodes = full_mention_data.get("nodes", [])
ment_links = full_mention_data.get("links", [])

int_nodes_df = pd.DataFrame(int_nodes)
int_links_df = pd.DataFrame(int_links)
ment_nodes_df = pd.DataFrame(ment_nodes)
ment_links_df = pd.DataFrame(ment_links)

print("Fehlende Werte interaction nodes:")
print(int_nodes_df.isnull().sum())
print("\nFehlende Werte interaction links:")
print(int_links_df.isnull().sum())

print("\nFehlende Werte mention nodes:")
print(ment_nodes_df.isnull().sum())
print("\nFehlende Werte mention links:")
print(ment_links_df.isnull().sum())

Fehlende Werte interaction nodes:
name      0
value     0
colour    0
dtype: int64

Fehlende Werte interaction links:
source    0
target    0
value     0
dtype: int64

Fehlende Werte mention nodes:
name      0
value     0
colour    0
dtype: int64

Fehlende Werte mention links:
source    0
target    0
value     0
dtype: int64

print("Duplikate bei interaction nodes:")
print(int_nodes_df.duplicated().sum())
print("\nDuplikate be interaction links:")
print(int_links_df.duplicated().sum())

print("\nDuplikate bei mentions nodes:")
print(ment_nodes_df.duplicated().sum())
print("\nDuplikate bei mentions links:")
print(ment_links_df.duplicated().sum())

Duplikate bei interaction nodes:
0

Duplikate be interaction links:
0

Duplikate bei mentions nodes:
0

Duplikate bei mentions links:
0

Wir haben im Datensatz keine fehlenden oder doppelt vorkommende Werte, was uns das weitere Vorgehen vereinfacht, da man keine Datenimputation oder ähnliches verwenden muss.

plt.figure(figsize=(14, 6))
plt.subplot(1, 2, 1)
plt.hist(int_nodes_df["value"], bins=30, alpha=0.7, label="Interactions")
plt.title("Verteilung der Interaktionen")
plt.xlabel("Interaktionen")
plt.ylabel("Häufigkeit")
plt.legend()

plt.subplot(1, 2, 2)
plt.hist(ment_nodes_df["value"], bins=30, alpha=0.7, color="orange", label="Mentions")
plt.title("Verteilung der Erwähnungen")
plt.xlabel("Erwähnungen")
plt.ylabel("Häufigkeit")
plt.legend()
plt.tight_layout()
plt.show()

Der mention Datensatz scheint sich viel mehr auf andere Charaktere zu beziehen als beim Interaktionsdatensatz. Dies macht auch Sinn, da viel mehr eine Person erwähnt wird als tatsächlich getroffen wird.

print(f"Durchschnittliche Interaktionen: {round(int_nodes_df['value'].mean(), 1)}")
print(f"Durchschnittliche Erwähnungen: {round(ment_nodes_df['value'].mean(), 1)}")

Durchschnittliche Interaktionen: 22.1
Durchschnittliche Erwähnungen: 34.7

2.2 Interaktionen

int_graph = nx.Graph()
ment_graph = nx.Graph()

for node in int_nodes:
    int_graph.add_node(node['name'])
for link in int_links:
    source_name = int_nodes[link['source']]['name']
    target_name = int_nodes[link['target']]['name']
    int_graph.add_edge(source_name, target_name, weight=link['value'])


for node in ment_nodes:
    ment_graph.add_node(node['name'])

for link in ment_links:
    source_name = ment_nodes[link['source']]['name']
    target_name = ment_nodes[link['target']]['name']
    ment_graph.add_edge(source_name, target_name, weight=link['value'])

# Plot the network
plt.figure(figsize=(15, 10))
plt.title("Star Wars Interaction Netzwerk", fontsize=16)
node_size = 300
node_colors = "lightBlue"

pos = nx.spring_layout(int_graph, seed=42, k=0.5)
nx.draw_networkx_nodes(
    int_graph,
    pos,
    node_size=node_size,
    node_color=node_colors,
    alpha=0.9
)
nx.draw_networkx_edges(
    int_graph,
    pos,
    width=0.5,
    edge_color="gray",
    alpha=0.5
)
nx.draw_networkx_labels(
    int_graph,
    pos,
    font_size=8,
    font_color="black",
    font_weight="bold"
)

plt.axis("off")
plt.show()
# print anzahl interaktionen
print("Anzahl Interaktionen:", int_graph.number_of_edges())

# print anzahl nodes
print("Anzahl Nodes interaction:", int_graph.number_of_nodes())

Anzahl Interaktionen: 450
Anzahl Nodes interaction: 112

In der Grafik der Interaktionen sehen wir viele Verbindungen zwischen den Charakteren. Dies sind die Interaktionen zwischen den Charakteren über alle sieben Star Wars Filme hinweg.

Auch ist im Print zu sehen, dass man insgesammt im Netzwerk 450 Interaktionen hat. Am Rande des Netzwerk sehen wir einige Charaktere, welche nur eine Interaktion haben. Im Zentrum hingegen gibt es Charaktere, welche sehr viele Interaktionen haben und somit auf den ersten Blick als "wichtig" gesehen werden.

2.3 Erwähnungen

# Plot the network
plt.figure(figsize=(15, 10))
plt.title("Star Wars mention Netzwerk", fontsize=16)
node_size = 300
node_colors = "orange"

pos = nx.spring_layout(ment_graph, seed=42, k=0.8)
nx.draw_networkx_nodes(
    ment_graph,
    pos,
    node_size=node_size,
    node_color=node_colors,
    alpha=0.9
)
nx.draw_networkx_edges(
    ment_graph,
    pos,
    width=0.5,
    edge_color="gray",
    alpha=0.5
)
nx.draw_networkx_labels(
    ment_graph,
    pos,
    font_size=8,
    font_color="black",
    font_weight="bold"
)

plt.axis("off")
plt.show()
#print anzahl erwähnungen
print("Anzahl Erwähnungen:", ment_graph.number_of_edges())

# print anzahl nodes
print("Anzahl Nodes Erwähnungen:", ment_graph.number_of_nodes())

Anzahl Erwähnungen: 817
Anzahl Nodes Erwähnungen: 113

Im vergleich zu den Interaktionen sehen wir in dem Netzwerk der Erwähnungen viel mehr Kanten. Genau gesagt sind es 817 Kanten, wobei jede Kante für eine Erwähnung steht. Allerdings macht dies auch Sinn, da eine Erwähnung viel schneller passiert als eine Interaktion.

Auch hier sehen wir, dass es einige Charaktere gibt, welche sich am Rande des Netzwerkes befinden und nur 1-2 Erwähnungen besitzen. Ebenfalls sind hier im Zentrum des Netzewerkes wieder "wichgigere" Figuren, welche sehr viele Kanten/Erwähnungen haben.

3 Communities

Im Star Wars-Universum treibt der Imperator seine Pläne voran, die gesamte Galaxie unter seine Kontrolle zu bringen. Unsere Aufgabe ist es, herauszufinden, welche Figuren er als nächstes eliminieren möchte. Sein Ziel ist es, wichtige Charaktere auszuschalten, die ihm bei seinen Plänen in die Quere kommen könnten. Dies könnte dem Imperator gelingen in dem er mit seinem Data Science Team die Gegner analysiert und zentrale Figuren identifizieren könnte.

Um dies zu erreichen und die Charaktere warnen zu können, setzen wir auf Clustering-Methoden, die uns helfen, die Netzwerke seiner Feinde zu durchleuchten. Wir vergleichen zwei Ansätze: Louvain und Label Propagation. Anhand der Ergebnisse entscheiden wir, welcher Algorithmus für unsere Ziele am effektivsten ist.

3.1 Subgraphen

Bevor wir mit dem Clustering beginnen müssen wir noch untersuchen, ob es schon kleine subgraphen gibt.

connected_components = list(nx.connected_components(int_graph))
num_components = len(connected_components)
component_sizes = [len(component) for component in connected_components]

plt.figure(figsize=(6, 5))
plt.bar(range(1, num_components + 1), component_sizes)
plt.xlabel("Graphen")
plt.ylabel("Anzahl der Knoten")
plt.title("Verbundene Komponenten und Knotengrössen im interactions Netzwerk")
plt.xticks(range(1, num_components + 1))
plt.show()

Eine Node scheint keine Interaktionen zu haben. Dies könnte ein Fehler in den Daten sein. Um herauszufinden, welche Figur dort ist, werden wir diese ausgeben.

connected_components[1]

{'GOLD FIVE'}

Gold five ist ein Pilot der Rebellenallianz und hat keine Interaktionen. Dies könnte ein Fehler in den Daten sein. Aus dem Grund wird er aus dem Netzwerk entfernt.

int_graph.remove_node('GOLD FIVE')

connected_components = list(nx.connected_components(int_graph))
num_components = len(connected_components)

print(f"Anzahl Netzwerke nach bereinigung: {num_components}")

Anzahl Netzwerke nach bereinigung: 1

Nun ist nurnoch 1 Netzwerk vorhanden, da wir den "Gold Five" entfernt haben.

connected_components = list(nx.connected_components(ment_graph))
num_components = len(connected_components)
component_sizes = [len(component) for component in connected_components]

plt.figure(figsize=(6, 5))
plt.bar(range(1, num_components + 1), component_sizes)
plt.xlabel("Graphen")
plt.ylabel("Anzahl der Knoten")
plt.title("Verbundene Komponenten und Knotengrössen im mention Netzwerk")
plt.xticks(range(1, num_components + 1))
plt.show()

3.2 Label propagation interaction Datensatz

Label Propagation ist ein Algorithmus, der Labels in einem Netzwerk (Graph) verteilt. Einige Knoten im Graph haben bereits Labels, die bekannt sind, während die anderen keine haben. Der Algorithmus funktioniert so:

1. Start: Die Knoten mit Labels behalten ihre Werte, und unbeschriftete Knoten starten mit einem leeren Label oder einem zufälligen Wert.
2. Propagation: In mehreren Durchgängen erhält jeder Knoten das Label, das bei seinen Nachbarn am häufigsten vorkommt.
3. Wiederholung: Dieser Prozess wird wiederholt, bis die Labels sich nicht mehr ändern oder eine maximale Anzahl von Durchgängen erreicht ist.
   Das Ziel ist, dass ähnliche Knoten (die nah beieinander oder stark verbunden sind) am Ende dasselbe Label haben. Der Algorithmus nutzt also die Struktur des Graphen, um die Labels zu verbreiten.

label_propagation_communities_result = list(nx.algorithms.community.label_propagation_communities(int_graph))
num_label_propagation_communities = len(label_propagation_communities_result)
distinct_colors_lp = [plt.cm.tab20(i / num_label_propagation_communities) for i in range(num_label_propagation_communities)]

label_propagation_color_map = {}
for i, community in enumerate(label_propagation_communities_result):
    for node in community:
        label_propagation_color_map[node] = distinct_colors_lp[i]

node_colors_label_propagation = [label_propagation_color_map[node] for node in int_graph.nodes]

plt.figure(figsize=(15, 15))
pos_label_propagation = nx.spring_layout(int_graph, seed=42, k=3)
nx.draw_networkx_nodes(int_graph, pos_label_propagation, node_color=node_colors_label_propagation, node_size=100, alpha=0.9)
nx.draw_networkx_edges(int_graph, pos_label_propagation, alpha=0.5)
nx.draw_networkx_labels(int_graph, pos_label_propagation, font_size=8, font_color='black')
plt.title("Clusters nach Labelpropagation auf interactions", fontsize=18)
plt.axis('off')
plt.show()

print(f"Anzahl gefundener Clusters {len(label_propagation_communities_result)}")

Anzahl gefundener Clusters 7

fig, axes = plt.subplots(2, 4, figsize=(16, 10))
axes = axes.flatten()
for i, community in enumerate(label_propagation_communities_result):
    if i >= 2 * 4:
        break
    subgraph = int_graph.subgraph(community)
    pos_subgraph = nx.spring_layout(subgraph, seed=42, k=3)
    ax = axes[i]
    nx.draw_networkx_nodes(subgraph, pos_subgraph, node_color=[distinct_colors_lp[i]] * len(subgraph),node_size=100, alpha=0.9, ax=ax)
    nx.draw_networkx_edges(subgraph, pos_subgraph, alpha=0.5, ax=ax)
    nx.draw_networkx_labels(subgraph, pos_subgraph, font_size=8, font_color='black', ax=ax)
    ax.set_title(f"Community {i + 1}", fontsize=12)
    ax.axis('off')

    # Hide any unused subplots
for j in range(i + 1, len(axes)):
    axes[j].axis('off')

Wir sehen das sich mit dem Label-Propagation-Algorithmus 7 Communitys auf den interaction Datensatz.

• Community 1: In der ersten Community sehen wir ein sehr dichtes Netzwerk mit vielen Charakteren vorallem aus dem Filmen 1-6. Es ist eine Durchmischung aus Antagonisten z.B. General grievos oder den Hauptfigueren wie Luke Skywalker.
• Community 2: Diese Gruppe enthält Charaktere wie Finn, Rey und Poe. Diese Gruppe setzt sich aus Charakteren zusammen die im Film 7 vorkommen und nicht so stark verknüpf sind mit den Filmen 1-6.
• Community 3: Diese Community beinhaltet Charaktere wie Wedge, Biggs, und Red Leader, die in den Raumschlachten in den Filmen 1-6 präsent sind.
• Community 4: Diese Community hat Tarkin und Motti, wichtige Figuren des Galaktischen Imperiums und sind Generäle.
• Community 5: Diese Community setzt sich aus Adimräle des Imperium zusammen.
• Community 6: Diese Community scheint vorallem "böse" Charaktere aus dem 7-ten Film zu haben. Wie z.B. Snoke der oberste Anführer ist.
• Community 7: Diese Community enthält Charaktere wie Ello Asty, Jess und andere, die in den Sequels als Nebenfiguren agieren, insbesondere Piloten der Rebellen/Resistance.

Der Label-Propagation-Algorithmus unterscheidet erfolgreich zwischen den Charaktergruppen der Filme 1-6 und der Episode 7. Dies macht Sinn, da die Filme 1–6 eine zusammenhängende Storyline verfolgen, die sich auf die Entwicklung der Skywalker-Saga konzentriert, während Episode 7 eine neue Saga mit frischen Charakteren einführt. Darüber hinaus war der Algorithmus auch in der Lage, eine Trennung zwischen wichtigen und nebensächlichen Charakteren vorzunehmen. Community 3 und 7 sind die Piloten von den Filmen 1-6 und Film 7 was auch interessant ist.Auch bei dieser Trennung gibt es Nebenfiguren einmal für die Filme 1-6 und 7. Eine etwas spezielle Unterscheidung ist das Community 4 und 5 beide Imperiale positionen haben einmal sind es Genrälre und die anderen Admirale. Diese Unterschiedung ist etwas speziell.

3.3 Label propagation mention Datensatz

label_propagation_communities_result = list(nx.algorithms.community.label_propagation_communities(ment_graph))
num_label_propagation_communities = len(label_propagation_communities_result)
distinct_colors_lp = [plt.cm.tab20(i / num_label_propagation_communities) for i in range(num_label_propagation_communities)]

label_propagation_color_map = {}
for i, community in enumerate(label_propagation_communities_result):
    for node in community:
        label_propagation_color_map[node] = distinct_colors_lp[i]

node_colors_label_propagation = [label_propagation_color_map[node] for node in ment_graph.nodes]

plt.figure(figsize=(15, 15))
pos_label_propagation = nx.spring_layout(ment_graph, seed=42, k=3)
nx.draw_networkx_nodes(ment_graph, pos_label_propagation, node_color=node_colors_label_propagation, node_size=100, alpha=0.9)
nx.draw_networkx_edges(ment_graph, pos_label_propagation, alpha=0.5)
nx.draw_networkx_labels(ment_graph, pos_label_propagation, font_size=8, font_color='black')
plt.title("Clusters nach Labelpropagation auf mention", fontsize=18)
plt.axis('off')
plt.show()

print(f"Anzahl gefundener Clusters {len(label_propagation_communities_result)}")

Anzahl gefundener Clusters 4

fig, axes = plt.subplots(2, 2, figsize=(16, 10))
axes = axes.flatten()
for i, community in enumerate(label_propagation_communities_result):
    if i >= 2 * 2:
        break
    subgraph = ment_graph.subgraph(community)
    pos_subgraph = nx.spring_layout(subgraph, seed=42, k=3)
    ax = axes[i]
    nx.draw_networkx_nodes(subgraph, pos_subgraph, node_color=[distinct_colors_lp[i]] * len(subgraph),
                           node_size=100, alpha=0.9, ax=ax)
    nx.draw_networkx_edges(subgraph, pos_subgraph, alpha=0.5, ax=ax)
    nx.draw_networkx_labels(subgraph, pos_subgraph, font_size=8, font_color='black', ax=ax)
    ax.set_title(f"Community {i + 1}", fontsize=12)
    ax.axis('off')

Der Label-Propagation-Algorithmus auf dem mention Datensatz konnte 4 Communitys finden.

• Community 1: Dies scheinen vorallem Charaktere aus den Filem 1-6 zu sein.
• Community 2: Diese Charaktere sind vorallem Charaktere aus dem Film 7.
• Community 3: Ist die Naberrie Familie. Dies ist die Familie von Padmee eine der Hauptcharaktere welche nur erwähnt werden.
• Community 4: Dies sind Piloten aus dem Film 7

Besonders interessant ist die Community 3, die ausschliesslich auf Mentions basiert. Diese Community stellt die Familie von Padmé Amidala dar, was zeigt, dass sie zwar kaum physisch präsent ist, jedoch durch Erwähnungen eine Rolle im narrativen Kontext spielt. Die Gruppe von Piloten in der Darstellung ist ebenfalls bemerkenswert. Ihre Bündelung in einer Community lässt darauf schliessen, dass Piloten, insbesondere im Kontext von Episode 7, stärker thematisiert werden. Dies zeigt das die Flug kämpfe mehr im der Fokus im Film liegen, wodurch die Piloten als Gruppe präsenter und stärker verknüpft auftreten. Die zweite Community, die mehrheitlich Charaktere aus Episode 7 enthält, überrascht mit dem Auftauchen von Darth Vader. Obwohl er physisch nicht mehr präsent ist (Spoiler: er stirbt in Episode 6), bleibt er eine zentrale Figur durch seinen Einfluss auf Kylo Ren, dessen Charakter stark von Vaders Vermächtnis geprägt ist. Vaders häufige Erwähnung unterstreicht, wie vergangene Ereignisse und verstorbene Charaktere in einer neuen Erzählung eine treibende Kraft sein können und die Verbindung zwischen den Filmen aufrechterhalten.

3.4 Louvain Algorithmus auf interaction Datensatz

Der Louvain-Algorithmus ist ein iteratives Verfahren zur Identifikation von Community-Strukturen in Graphen. Der Algorithmus gehört zu den Greedy-Verfahren, bei denen Entscheidungen basierend auf dem aktuellen Optimierungspotential getroffen werden. Das Ziel des Louvain-Algorithmus ist es, die sogenannte Modularität zu maximieren, eine Metrik, die die Dichte der Verbindungen innerhalb von Communities mit denen zwischen Communities vergleicht. Ablauf des Louvain-Algorithmus:

• Modularity Optimization (Phase 1): Zu Beginn wird jeder Knoten einer eigenen Community zugeordnet. Iterativ wird für jeden Knoten überprüft, ob sich die Modularity verbessert, wenn der Knoten aus seiner aktuellen Community entfernt und einer Nachbar-Community zugewiesen wird. Diese Zuweisung erfolgt so, dass der Modularity-Wert maximal steigt. Dieser Schritt wird für alle Knoten wiederholt, bis keine weitere Verbesserung der Modularity möglich ist.
• Community Aggregation (Phase 2): In dieser Phase werden die Communities aus der ersten Phase zu neuen "Superknoten" zusammengefasst. Die Gewichte der Kanten zwischen den neuen Knoten repräsentieren die Anzahl der Verbindungen zwischen den ursprünglichen Communities. Dieser reduzierte Graph wird dann wieder durch die erste Phase (Modularity Optimization) verarbeitet.
• Iterative Wiederholung: Die beiden Schritte werden wiederholt, bis keine signifikante Verbesserung der Modularity mehr erreicht wird.

Modularitätsformel Die Modularität ( Q ) wird wie folgt berechnet:

$$ Q = \frac{1}{2m} \sum_{ij} \left( A_{ij} - \frac{k_i k_j}{2m} \right) \delta(c_i, c_j) $$

Bedeutung der Variablen:

• $Q$: Der Modularitätswert, der die Qualität der Community-Aufteilung beschreibt.
• $A_{ij}$: Gewicht der Kante zwischen den Knoten $i$ und $j$.
• $k_i$: Summe der Gewichte aller Kanten, die vom Knoten $i$ ausgehen ($k_i = \sum_j A_{ij}$).
• $m$: Gesamtes Kantengewicht im Graphen.
• $\delta(c_i, c_j)$: Indikatorfunktion, die $1$ ist, wenn die Knoten $i$ und $j$ derselben Community $c$ angehören, sonst $0$.

Die Maximierung der Modularität bedeutet, dass möglichst viele Verbindungen innerhalb von Communities und möglichst wenige Verbindungen zwischen Communities liegen.

louvain_communities_result = louvain_communities(int_graph, seed=42)
num_louvain_communities = len(louvain_communities_result)

louvain_colors = plt.cm.rainbow(range(num_louvain_communities))
louvain_color_map = {}

for community_index, community_nodes in enumerate(louvain_communities_result):
    for node in community_nodes:
        louvain_color_map[node] = louvain_colors[community_index % len(louvain_colors)]

node_colors_louvain = [louvain_color_map[node] for node in int_graph.nodes]

distinct_colors = [plt.cm.tab20(i / num_louvain_communities) for i in range(num_louvain_communities)]
node_colors_louvain_distinct = []
for node in int_graph.nodes:
    for i, community in enumerate(louvain_communities_result):
        if node in community:
            node_colors_louvain_distinct.append(distinct_colors[i])

plt.figure(figsize=(15, 15))
pos_louvain = nx.spring_layout(int_graph, seed=42, k=3)
nx.draw_networkx_nodes(int_graph, pos_louvain, node_color=node_colors_louvain_distinct, node_size=100, alpha=0.9)
nx.draw_networkx_edges(int_graph, pos_louvain, alpha=0.5)
nx.draw_networkx_labels(int_graph, pos_louvain, font_size=8, font_color='black')
plt.title("Louvain Community auf interactions", fontsize=18)
plt.axis('off')
plt.show()

rows, cols = 2, 3
fig, axes = plt.subplots(rows, cols, figsize=(16, 10))
axes = axes.flatten()
for i, community in enumerate(louvain_communities_result):
    if i >= rows * cols:
        break
    subgraph = int_graph.subgraph(community)
    pos_subgraph = nx.spring_layout(subgraph, seed=42, k= 3)
    ax = axes[i]
    nx.draw_networkx_nodes(subgraph, pos_subgraph, node_color=[distinct_colors[i]] * len(subgraph),
                           node_size=100, alpha=0.9, ax=ax)
    nx.draw_networkx_edges(subgraph, pos_subgraph, alpha=0.5, ax=ax)
    nx.draw_networkx_labels(subgraph, pos_subgraph, font_size=8, font_color='black', ax=ax)
    ax.set_title(f"Community {i + 1}", fontsize=12)
    ax.axis('off')

for j in range(i + 1, len(axes)):
    axes[j].axis('off')

Wir sehen das sich mit dem Louvain Algorithmus 6 Communitys auf den interaction Datensatz.

• Community 1: Die erste Community ist durch ein grosses, dichtes Netzwerk gekennzeichnet, ähnlich wie beim Label Propagation Algorithmus. Sie umfasst eine Vielzahl von Schlüsselcharakteren wie Obi-Wan Kenobi, Yoda, Anakin Skywalker etc. .
• Community 2: In der zweiten Community finden sich Charaktere, die eher Nebenrollen einnehmen, aber dennoch entscheidend für die Handlung der Episode 4 sind. Dazu gehören Mitglieder von Luke Skywalkers Adoptivfamilie wie Beru Whitesun, Owen Lars und Cliegg Lars. Diese Figuren repräsentieren den Ausgangspunkt von Luke Skywalkers Kindheit.
• Community 3: Diese Community wird von den "bösen" Charakteren dominiert. Im Mittelpunkt steht Darth Vader, umgeben von imperialen Generälen und Schurken wie Tarkin, Jerjerrod, Ozzel und Needa. Auch Kopfgeldjäger wie Boba Fett und Jango Fett sind hier vertreten. Diese Gruppe spiegelt die Hierarchie und die Machtstrukturen des Galaktischen Imperiums wider und steht symbolisch für den Konflikt, der die gesamte Saga durchzieht.
• Community 4: Die vierte Community konzentriert sich auf die Piloten und Rebellionsmitglieder, die in den Episoden 1-6 vorkommen. Charaktere wie Wedge Antilles, Biggs Darklighter, Red Leader und Gold Leader stehen im Mittelpunkt dieser Gruppe.
• Community 5: In der fünften Community finden wir die zentralen Hauptcharaktere der Episoden 4-6(Rebellion). Dazu zählen Luke Skywalker, Leia Organa, Han Solo, Chewbacca und die Droiden C-3PO und R2-D2. Auch Nebenfiguren wie Lando Calrissian und Admiral Ackbar sind hier eingegliedert, was die Bedeutung ihrer Rollen in der Rebellion unterstreicht.
• Community 6: Die sechste Community umfasst die Charaktere der 7 Episode und ist damit zeitlich und narrativ von den vorherigen Gruppen abgegrenzt. Hier finden sich Figuren wie Rey, Finn, Poe Dameron, Kylo Ren und der Droide BB-8. Auch wichtige Nebencharaktere wie Maz Kanata, General Hux und Supreme Leader Snoke gehören zu dieser Gruppe. Diese Community zeigt die neue Generation von Helden und bösen.

Der Louvain-Algorithmus scheint vor allem die Charaktere aus den Filmen 4 bis 6 klar danach unterscheiden zu können, ob sie gut oder böse sind. Auffällig ist, dass wichtige Generäle ebenfalls in das Netzwerk der Hauptcharaktere in der fünften Community eingebunden sind. Eine weitere Auffälligkeit ist, das Jabba der eigentlich ein Anführere einer Verbrecherorganisation ist. Das könnte darauf zurück zuführen sein, das er nur mit den Hauptcharakteren (Luke, Leia und Han Solo) interagiert. Dies könnte darauf hinweisen, wie bedeutend diese Figuren für die Hauptcharaktere und deren Handlungen sind. Ähnlich wie der Label Propagation Algorithmus identifiziert der Louvain-Algorithmus auch ein separates Netzwerk für die Piloten.
Die Charaktere aus den Filmen 1 bis 3 bleiben hingegen eng miteinander verknüpft, unabhängig davon, ob sie gut oder böse sind. Das ergibt Sinn, da diese Figuren innerhalb dieser Filme stark miteinander verbunden sind. Ein Beispiel dafür ist der Sith (böse), Count Dooku, der der Meister des Jedi Qui-Gon Jinn (gut) war.
Eine weitere interessante Community ist die zweite Gruppe, die sich aus den Adoptiveltern von Luke zusammensetzt. Ausserdem wurde eine sechste Community identifiziert, die aus den Charakteren des siebten Films besteht. Hierbei ist besonders interessant, dass keine klare Unterscheidung zwischen gut und böse gemacht werden konnte, was die Eigenständigkeit und thematische Abgrenzung des siebten Films von den vorherigen Teilen unterstreicht.

3.5 Louvain Algorithmus auf mention Datensatz

louvain_communities_result = louvain_communities(ment_graph, seed=42)
num_louvain_communities = len(louvain_communities_result)

louvain_colors = plt.cm.rainbow(range(num_louvain_communities))
louvain_color_map = {}

for community_index, community_nodes in enumerate(louvain_communities_result):
    for node in community_nodes:
        louvain_color_map[node] = louvain_colors[community_index % len(louvain_colors)]

node_colors_louvain = [louvain_color_map[node] for node in ment_graph.nodes]

distinct_colors = [plt.cm.tab20(i / num_louvain_communities) for i in range(num_louvain_communities)]
node_colors_louvain_distinct = []
for node in ment_graph.nodes:
    for i, community in enumerate(louvain_communities_result):
        if node in community:
            node_colors_louvain_distinct.append(distinct_colors[i])

plt.figure(figsize=(15, 15))
pos_louvain = nx.spring_layout(ment_graph, seed=42, k=3)
nx.draw_networkx_nodes(ment_graph, pos_louvain, node_color=node_colors_louvain_distinct, node_size=100, alpha=0.9)
nx.draw_networkx_edges(ment_graph, pos_louvain, alpha=0.5)
nx.draw_networkx_labels(ment_graph, pos_louvain, font_size=8, font_color='black')
plt.title("Louvain Community auf mention", fontsize=18)
plt.axis('off')
plt.show()

rows, cols = 2, 3
fig, axes = plt.subplots(rows, cols, figsize=(16, 10))
axes = axes.flatten()
for i, community in enumerate(louvain_communities_result):
    if i >= rows * cols:
        break
    subgraph = ment_graph.subgraph(community)
    pos_subgraph = nx.spring_layout(subgraph, seed=42, k= 3)
    ax = axes[i]
    nx.draw_networkx_nodes(subgraph, pos_subgraph, node_color=[distinct_colors[i]] * len(subgraph),
                           node_size=100, alpha=0.9, ax=ax)
    nx.draw_networkx_edges(subgraph, pos_subgraph, alpha=0.5, ax=ax)
    nx.draw_networkx_labels(subgraph, pos_subgraph, font_size=8, font_color='black', ax=ax)
    ax.set_title(f"Community {i + 1}", fontsize=12)
    ax.axis('off')

for j in range(i + 1, len(axes)):
    axes[j].axis('off')

Der Louvain-Algorithmus auf dem mention Datensatz konnte 4 Communitys finden.

• Community 1: Die erste Community setz sich primär aus Charaktere aus den Filmen 1-3 zusammen. Zu den zentralen Figuren zählen Obi-Wan Kenobi, Anakin Skywalker und Yoda, die essenziell für die Handlung dieser Filme sind.
• Community 2: Die zweite Community besteht wie schon beim interaction Datensatz, aus einem kleinen, isolierten Netzwerk, das aus Beru Whitesun, Owen Lars und Cliegg Lars besteht.
• Community 3: Die dritte Community ist durch Charaktere aus dem Filmen 4-6 mit den zentralen Figuren Luke Skywalker und Darth Vader.
• Community 4: Die vierte Community setzt sich wieder aus den Charakteren aus dem 7ten Film zusammen.

Der Louvain-Algorithmus auf dem mention Datensatz unterscheidet die zusammenhänge Filmen sehr gut. Sprich Film 1-3, Film 4-6 und Film 7. Interessant ist sicher das wieder die Adoptive Eltern von Luke als eine Seperate Community zählt. Dies könnte wieder darauf zurück zuführen sein das nur Luke und Obiwan kontakt mit ihnen hatte.

Für die weitere Analyse werden wir den Louvain-Algorithmus nehmen. Dies aus dem Grund dass gut und böse unterschieden werden können und wir so diese Netzwerke weiter Analysieren können.

4 Aktor-Zentralität

Zentralitätsmasse auf der Ebene von Aktoren sagen aus, wie wichtig einzelne Knoten, aufgrund ihrer Position im Netzwerk sind. Ihre Position erlaubt es ihnen den Informationsfluss zu beeinflussen. Damit der Imperator das Universum unterjochen kann, verschafft er sich mithilfe von Aktor-Zentralitäten einen Überblick, welche Knoten wichtig sind, um sie dann entweder als verbündete zu gewinnen, oder zu eliminieren.

Interactions Datensatz

Der Datensatz Interactions enthält Interaktionen zwischen den einzelnen Charakteren über 7 Episoden.

Closeness

Die Closeness-Zentralität $C_C(i)$ ist, im Gegensatz zur Degree-Zentralität, kein lokales Mass, sondern berücksichtigt das gesamte Netzwerk. Zur Berechnung wird die Summe der kürzesten inversen Distanzen von einem Knoten $i$ zu allen anderen Knoten berechnet:

$$ C_C(i) = \sum_{j=0}^{N} d(i, j)^{-1} $$

Dabei gilt:

• $C_C(i)$: Closeness-Zentralität des Knotens $i$
• $d(i, j)$: Kürzeste Pfaddistanz zwischen den Knoten $i$ und $j$
• $N$: Gesamtanzahl der Knoten im Netzwerk

Die Closeness-Zentralität gibt an, wie effizient ein Knoten $i$ andere Knoten im Netzwerk erreichen kann. Anders ausgedrückt zeigt sie, wie effektiv $i$ Informationen im Netzwerk verbreitet, wobei stets die kürzesten Pfade berücksichtigt werden.

import importlib
import plots
importlib.reload(plots)

plots.plot_top_nodes_by_community(
    "data/starwars-full-interactions-allCharacters.json",
    centrality_type="closeness",
    top_n=5,
)

Der Plot zeigt pro Community die wichtigsten Knoten in Bezug auf effiziente Informationsverbreitung mit den höchsten Closeness-Zentralität-Werten.

Auffällig ist, dass für alle Communities ausser 2 und 3 die 3–4 Aktoren mit den höchsten Werten relativ nahe beieinander liegen.

Für den Imperator bedeutet dies mehr Handlungsspielraum. Er kann versuchen, bei den feindlichen Communities zuerst den Aktor mit der höchsten Zentralität auf seine Seite zu bringen. Falls dies scheitert, kann er die nächst kleineren Aktoren ansprechen, ohne grosse Einbussen bei der Bedeutung der Knoten.

Beispielsweise zeigt die Community 4 einen Aktor mit hoher Zentralität, gefolgt von drei weiteren mit kleiner aber unter sich gleicher Zentralität, bevor der Wert weiter abfällt. Der Imperator müsste nur einen der drei (Biggs, Gold Leader oder Red Leader) auf seine Seite ziehen, um mit der gleichen Effizienz in Community 4 Informationen zu verbreiten.

Falls die Strategie des Imperators jedoch darin besteht, Aktoren auszuschalten, hat er mehr Arbeit vor sich. Einen Aktor auszuschalten reicht hier nicht aus, da die übrigen dicht beieinander liegen und der Effekt kaum sichtbar wäre.

PS: Community 2 hat die gleichen Werte, weil es sich um ein Dreiecks-Netzwerk handelt.

Betweenness

Die Betweenness-Zentralität $C_B(i)$ misst, wie oft ein Knoten $i$ auf den kürzesten Pfaden zwischen anderen Knoten liegt. Sie wird berechnet als:

$$ C_B(i) = \sum_{s \neq i \neq t} {\sigma_{st}(i)} $$

Dabei gilt:

• $C_B(i)$: Betweenness-Zentralität des Knotens $i$
• $\sigma_{st}(i)$: Anzahl der kürzesten Pfade zwischen $s$ und $t$, die durch den Knoten $i$ verlaufen
• $s, t$: Beliebige Knoten im Netzwerk, wobei $s \neq t \neq i$

Die Betweenness-Zentralität zeigt, wie entscheidend ein Knoten $i$ als Bindeglied für den Informationsfluss im Netzwerk ist. Ein hoher Wert bedeutet, dass $i$ eine Schlüsselrolle bei der Verbindung von Knoten und der Unterbrechung oder Förderung von Verbindungen spielt.

importlib.reload(plots)

plots.plot_top_nodes_by_community(
    "data/starwars-full-interactions-allCharacters.json",
    centrality_type="betweenness",
    top_n=5,
)

Wir sehen, dass die Zentralitätswerte der Betweenness deutlich aussagekräftiger sind als die der Closeness. Dies zeigt sich daran, dass die Werte (rapide) zwischen dem ersten und dem n-ten Knoten abfallen.

Für den Imperator bedeutet dies, dass der zu beeinflussende Aktor eindeutig identifiziert und leichter ermittelt werden kann.

Ein Beispiel: Wenn man in jeder feindlichen Community die drei Knoten mit der höchsten Betweenness-Zentralität entfernt, werden die meisten Verbindungen unterbrochen, da diese Knoten als Bindeglieder zwischen den anderen fungieren.

Falls der Imperator hingegen versucht, die Knoten mit hoher Betweenness auf seine Seite zu ziehen, hat er weniger Handlungsspielraum. Wenn der erste Versuch scheitert, muss er den nächsten Knoten ansprechen, der eine geringere Zentralität aufweist und somit weniger bedeutend ist.

PS: Community 2 hat keinen Wert da es sich um ein Dreiecks-Netzwerk handelt.

Mentions Datensatz

Im Gegensatz zum Interactions-Datensatz geht es bei den Mentions darum, wie oft jemand erwähnt wurde. Dies lässt auf die allgemeine Wichtigkeit eines Charakters schliessen und weniger auf die Beziehungen zwischen den einzelnen Charakteren.

Daher ergibt es keinen Sinn, hier auf die Communities zu schauen, da sich “gute” und “böse” Charaktere sehr wahrscheinlich oft gegenseitig erwähnen. Bei den Interaktionen hingegen begegnen sie sich vermutlich weniger häufig, was zu klaren Community Strukturen führt.

Closeness

import importlib
import plots
importlib.reload(plots)

plots.plot_top_nodes_by_file(
    "data/starwars-full-mentions.json",
    centrality_type="closeness",
    top_n=10,
)

Betweenness

import importlib
import plots
importlib.reload(plots)

plots.plot_top_nodes_by_file(
    "data/starwars-full-mentions.json",
    centrality_type="betweenness",
    top_n=10,
)

Für die Closeness und Betweenness zeigt sich, ähnlich wie beim Interactions-Datensatz, ein vergleichbares Muster: Die Closeness-Werte liegen eng beieinander, da die Vernetzung im Netzwerk relativ homogen ist, während die Betweenness-Werte durch die zentrale Rolle weniger Knoten stark abnehmen.

In beiden Plots sind die fünf bis sechs wichtigsten Personen dieselben, jedoch in unterschiedlicher Reihenfolge. Für den Imperator wird somit klar, wen er auf seine Seite ziehen oder eliminieren müsste, falls Erwähnungen die Bedeutung von Charakteren widerspiegeln.

5 Link Prediction

Um die Reichweite des Imperators in seinem Sozialen Netzwerk zu vergrössern, verwendet sein Team die Macht von Link Prediction. Somit wollen sie für nicht-verbundene Knoten eine passende Verbindung finden, um das Netzwerk zu vergrössern. Die Link-predictions werden auf das gesammte Netzwerk angewendet unsd nicht nur auf einen bestimmten Knoten. So kann der Imperator über das ganze Netzwerk hinweg sehen, wo sich in naher Zukunft eine Verbindung bilden könnte.

Link Prediction ist eine Methode aus der Sozialen Netzwerkanalyse, welche basierend auf bestehenden Beziehungen und Netzwerkstrukturen vorhersagt, welche momentan unverbundenen Knoten zukünftig verknüpft werden könnten. Hier wird die Link Prediciton mittels unterschiedlichen Metriken auf den ersten Star Wars Film angewendet um später vergleichen zu können, ob die Links über den Verlauf der sieben Filme tatsächlich so zu Stande gekommen ist.

with open('data/starwars-episode-1-interactions-allCharacters.json') as f:
    data_interactions = json.load(f)

# Graph erstellen
G = nx.Graph()

for node in data_interactions['nodes']:
    G.add_node(node['name'])

for link in data_interactions['links']:
    src_id = link['source']
    tgt_id = link['target']
    source_name = data_interactions['nodes'][src_id]['name']
    target_name = data_interactions['nodes'][tgt_id]['name']
    G.add_edge(source_name, target_name)

print(G)

Graph with 38 nodes and 135 edges

5.1 Common Neighbours

Common Neighbours ist eine Methode der Link Prediction die misst, wie viele gemeinsame Nachbarn zwei Knoten haben. Je mehr gemeinsame Nachbarn vorhanden sind, desto höher ist die Wahrscheinlichkeit, dass zwischen den beiden Knoten eine neue Verbindung entsteht.

Die Formel dazu lautet:

$$ \text{common\_neighbours}(X, Y) = \bigl| N(X) \cap N(Y) \bigr| $$

Wobei N die Anzahl Nachbarn angibt.

# Link-Prediction mit Common Neighbours
potential_links = []
nodes = list(G.nodes())
n = len(nodes)

for i in range(n):
    for j in range(i+1, n):
        u = nodes[i]
        v = nodes[j]
        if not G.has_edge(u, v):
            cn_count = len(list(nx.common_neighbors(G, u, v)))
            if cn_count > 0:
                potential_links.append((u, v, cn_count))

potential_links.sort(key=lambda x: x[2], reverse=True)

print("Top 10 Link Predictions basierend auf Common Neighbours mit Namen:")
for u, v, score in potential_links[:10]:
    print(f"{u} - {v}: gemeinsame Nachbarn = {score}")

Top 10 Link Predictions basierend auf Common Neighbours mit Namen:
NUTE GUNRAY - JAR JAR: gemeinsame Nachbarn = 5
OBI-WAN - EMPEROR: gemeinsame Nachbarn = 5
OBI-WAN - SEBULBA: gemeinsame Nachbarn = 5
OBI-WAN - KITSTER: gemeinsame Nachbarn = 5
OBI-WAN - JABBA: gemeinsame Nachbarn = 5
OBI-WAN - RABE: gemeinsame Nachbarn = 5
CAPTAIN PANAKA - SHMI: gemeinsame Nachbarn = 5
SIO BIBBLE - BOSS NASS: gemeinsame Nachbarn = 5
SIO BIBBLE - ANAKIN: gemeinsame Nachbarn = 5
BOSS NASS - RIC OLIE: gemeinsame Nachbarn = 5

# Welcher NOde kommt wie oft vor in den top 10
top_nodes = [u for u, _, _ in potential_links[:10]]
top_nodes += [v for _, v, _ in potential_links[:10]]
top_nodes = dict.fromkeys(top_nodes, 0)

for u, v, _ in potential_links[:10]:
    top_nodes[u] += 1
    top_nodes[v] += 1

print("Häufigkeit der Top 10 Nodes in Link Predictions:")

for node, count in sorted(top_nodes.items(), key=lambda x: x[1], reverse=True):
    print(f"{node}: {count}")

Häufigkeit der Top 10 Nodes in Link Predictions:
OBI-WAN: 5
SIO BIBBLE: 2
BOSS NASS: 2
NUTE GUNRAY: 1
CAPTAIN PANAKA: 1
JAR JAR: 1
EMPEROR: 1
SEBULBA: 1
KITSTER: 1
JABBA: 1
RABE: 1
SHMI: 1
ANAKIN: 1
RIC OLIE: 1

Unter den Top 10 Link predictions mittels Common Neighbours, haben alle den gleichen Score. Besonders häfig ist Obi-Wan in den top Link Predictions vertreten, was Sinn macht, da er einer der Hauptfiguren aus Star Wars ist.

Nun wollen wir die predicteten Links noch visuell darstellen.

# Positionen der Knoten berechnen
pos = nx.spring_layout(G)

# Abmessungen für den Plot
plt.figure(figsize=(12, 6))

# Plot 1: Netzwerk mit Link Prediction (Common Neighbours)
plt.subplot(121)  # Erstelne von zwei Subplots
nx.draw(G, pos, with_labels=True, font_size=8, node_size=400)
nx.draw_networkx_edges(G, pos, edgelist=potential_links[:10], edge_color='r', width=2)
plt.title("Star Wars Episode 1 Interaction Network\nwith Common Neighbours")

# Plot 2: Netzwerk ohne Link Prediction
plt.subplot(122)
nx.draw(G, pos, with_labels=True, font_size=8, node_size=400)
plt.title("Star Wars Episode 1 Interaction Network")

# plot zeigen
plt.tight_layout()
plt.show()
print(G)

Graph with 38 nodes and 135 edges

In der Grafik ist gut zu sehen, dass die meisten Link-predictions eher im Zentrum des Netzwerks sind. Dies macht durchaus Sinn, da dort bereits die Meisten verknüpfungen bestehen und somit durch Common Neighbours viele Predictions gemacht werden können.

5.2 Jaccard Coefficient

Die Jaccarcd Coefficient Metrik ist eine Erweiterung der Common Neighbours Metrik. Sie berücksichtigt nicht nur die Anzahl gemeinsamer Nachbarn zweier Knoten, sondern setzt diese ins Verhältnis zu der Anzahl Nachbarn beider Knoten.

Die Formel für die Jaccard Coefficient lautet wie folgt:

$ \text{jaccard\_coefficient}(X, Y) = \frac{\lvert N(X) \cap N(Y) \rvert}{\lvert N(X) \cup N(Y) \rvert} $

with open('data/starwars-episode-1-interactions-allCharacters.json') as f:
    data_interactions = json.load(f)

# Erstellen des Graphen
G = nx.Graph()

for node in data_interactions['nodes']:
    G.add_node(node['name'])

for link in data_interactions['links']:
    src_id = link['source']
    tgt_id = link['target']
    source_name = data_interactions['nodes'][src_id]['name']
    target_name = data_interactions['nodes'][tgt_id]['name']
    G.add_edge(source_name, target_name)

# Jaccard-coefficient bererechnen
jaccard_scores = list(nx.jaccard_coefficient(G))

jaccard_scores.sort(key=lambda x: x[2], reverse=True)

# Top 10 ausgeben
print("Top 10 Link Predictions basierend auf Jaccard Coefficient:")
for u, v, score in jaccard_scores[:10]:
    print(f"{u} - {v}: Jaccard = {score:.4f}")

# Graph anzeigen
print(G)

Top 10 Link Predictions basierend auf Jaccard Coefficient:
RIC OLIE - BOSS NASS: Jaccard = 0.6250
SIO BIBBLE - BOSS NASS: Jaccard = 0.6250
RUNE - GENERAL CEEL: Jaccard = 0.6000
SHMI - BOSS NASS: Jaccard = 0.5556
R2-D2 - JIRA: Jaccard = 0.5000
FODE/BEED - SEBULBA: Jaccard = 0.5000
WATTO - JIRA: Jaccard = 0.5000
C-3PO - JIRA: Jaccard = 0.5000
JIRA - SEBULBA: Jaccard = 0.5000
JIRA - GREEDO: Jaccard = 0.5000
Graph with 38 nodes and 135 edges

# Welcher NOde kommt wie oft vor in den top 10
top_nodes = [u for u, _, _ in jaccard_scores[:10]]
top_nodes += [v for _, v, _ in jaccard_scores[:10]]
top_nodes = dict.fromkeys(top_nodes, 0)

for u, v, _ in jaccard_scores[:10]:
    top_nodes[u] += 1
    top_nodes[v] += 1

print("Top 10 Nodes in Link Predictions:")

for node, count in sorted(top_nodes.items(), key=lambda x: x[1], reverse=True):
    print(f"{node}: {count}")

Top 10 Nodes in Link Predictions:
JIRA: 5
BOSS NASS: 3
SEBULBA: 2
RIC OLIE: 1
SIO BIBBLE: 1
RUNE: 1
SHMI: 1
R2-D2: 1
FODE/BEED: 1
WATTO: 1
C-3PO: 1
GENERAL CEEL: 1
GREEDO: 1

Mit der Jaccard Coefficient Prediction sehen wir nun ein ganz anderes Resultat als bei der Common Neighbours Prediction. Es ist auffällig, dass der Obi Wan Charakter nun nicht mehr vorhanden ist. Dieser hat sich wohl entfernt, da er sehr viele Nachbarn hat und somit mittels Jaccard Coefficient weniger gewichtet wird. Hier werden die Charaktere "Jira" und "Boss Nass" relativ häufig mit neuen Links predicted.

# Positionen der Knoten berechnen
pos = nx.spring_layout(G)
 
plt.figure(figsize=(12, 6))

# Netzwerk mit Jaccard Link Prediction
plt.subplot(121)  
nx.draw(G, pos, with_labels=True, font_size=8, node_size=400)
nx.draw_networkx_edges(G, pos, edgelist=[(u, v) for u, v, _ in jaccard_scores[:10]], edge_color='r', width=2)
plt.title("Star Wars Episode 1 Interaction Network\nwith Jaccard Link Prediction")

# Netzwerk ohne Link Prediction
plt.subplot(122)  
nx.draw(G, pos, with_labels=True, font_size=8, node_size=400)
plt.title("Star Wars Episode 1 Interaction Network")

# Abbildung anzeigen
plt.tight_layout()  
plt.show()

Hier sehen wir visuell noch, dass Boss Nass und Jira einige Predicted Links erhalten haben durch den Jaccard Coefficient.

5.3 Resource Allocatoin

Der Ansatz bei der Resource Allocation basiert darauf, dass ein Knoten X Ressourcen (z. B. Informationen) über gemeinsame Nachbarn an einen nicht direkt verbundenen Knoten Z weiterleiten kann.

X sendet die Ressource an einen gemeinsamen Nachbarn Y, der sie gleichmässig auf alle seine Nachbarn verteilt. Hat Y viele Nachbarn, erhält Z nur einen kleinen Anteil der Ressource.

Die Formel für Resource Allocaton lautet: $$ \text{resource\_allocation}(X, Y) = \sum_{u \in N(X) \cap N(Y)} \frac{1}{|N(u)|} $$

with open('data/starwars-episode-1-interactions-allCharacters.json') as f:
    data_interactions = json.load(f)

G = nx.Graph()

# für alle links in data_interactions einen Knoten hinzufügen
for node in data_interactions['nodes']:
    G.add_node(node['name'])

for link in data_interactions['links']:
    src_id = link['source']
    tgt_id = link['target']
    source_name = data_interactions['nodes'][src_id]['name']
    target_name = data_interactions['nodes'][tgt_id]['name']
    G.add_edge(source_name, target_name)


# Resource Allocation
ra_scores = list(nx.resource_allocation_index(G))
ra_scores.sort(key=lambda x: x[2], reverse=True)

print("Top 10 Link Predictions basierend auf Resource Allocation:")
for u, v, score in ra_scores[:10]:
    print(f"{u} - {v}: RA = {score:.4f}")
print(G)

Top 10 Link Predictions basierend auf Resource Allocation:
OBI-WAN - RABE: RA = 0.5819
JAR JAR - NUTE GUNRAY: RA = 0.5778
RUNE - GENERAL CEEL: RA = 0.4409
OBI-WAN - NUTE GUNRAY: RA = 0.4369
TEY HOW - TC-14: RA = 0.4333
RUNE - DOFINE: RA = 0.4333
EMPEROR - OBI-WAN: RA = 0.4035
EMPEROR - TEY HOW: RA = 0.3500
TEY HOW - DARTH MAUL: RA = 0.3500
JAR JAR - BAIL ORGANA: RA = 0.3409
Graph with 38 nodes and 135 edges

# Welcher NOde kommt wie oft vor in den top 10
top_nodes = [u for u, _, _ in ra_scores[:10]]
top_nodes += [v for _, v, _ in ra_scores[:10]]
top_nodes = dict.fromkeys(top_nodes, 0)

for u, v, _ in ra_scores[:10]:
    top_nodes[u] += 1
    top_nodes[v] += 1

print("Top 10 Nodes in Link Predictions:")

for node, count in sorted(top_nodes.items(), key=lambda x: x[1], reverse=True):
    print(f"{node}: {count}")

Top 10 Nodes in Link Predictions:
OBI-WAN: 3
TEY HOW: 3
JAR JAR: 2
RUNE: 2
EMPEROR: 2
NUTE GUNRAY: 2
RABE: 1
GENERAL CEEL: 1
TC-14: 1
DOFINE: 1
DARTH MAUL: 1
BAIL ORGANA: 1

Mit der Resource Allocation gibt es keinen Charakter, welcher auffallend häufig gelinkt wird. Obi-Wan und Tey How haben hier die meisten Links erhalten, allerdings sind es jeweils nur drei.

# Positionen der Knoten berechnen
pos = nx.spring_layout(G)
plt.figure(figsize=(12, 6))

# Netzwerk mit RA Link Prediction
plt.subplot(121)  
nx.draw(G, pos, with_labels=True, font_size=8, node_size=400)
nx.draw_networkx_edges(G, pos, edgelist=[(u, v) for u, v, _ in ra_scores[:10]], edge_color='r', width=2)
plt.title("Star Wars Episode 1 Interaction Network\nwith Resource Allocation Link Prediction")

# Netzwerk ohne Link Prediction
plt.subplot(122) 
nx.draw(G, pos, with_labels=True, font_size=8, node_size=400)
plt.title("Star Wars Episode 1 Interaction Network")

# plot anzeigen
plt.tight_layout() 
plt.show()

5.4 Ademic Adar

Diese Metrik berechnet sich fast genau gleich wie Resource Allocation. Der einzige Unterschied ist, dass das Gewicht des Nenners abgeschwächt wird, indem da der Loga- rithmus verwendet wird:

$$ \text{adamic\_adar}(X, Y) = \sum_{u \in N(X) \cap N(Y)} \frac{1}{\ln(|N(u)|)} $$

Da die Metrik sehr ähnlich zu Resource Allocation ist, erwarten wir hier ein ähnliches Resultat.

with open('data/starwars-episode-1-interactions-allCharacters.json') as f:
    data_interactions = json.load(f)

G = nx.Graph()

for node in data_interactions['nodes']:
    G.add_node(node['name'])

for link in data_interactions['links']:
    src_id = link['source']
    tgt_id = link['target']
    source_name = data_interactions['nodes'][src_id]['name']
    target_name = data_interactions['nodes'][tgt_id]['name']
    G.add_edge(source_name, target_name)


# Adamic-Adar
aa_scores = list(nx.adamic_adar_index(G))
aa_scores.sort(key=lambda x: x[2], reverse=True)

print("Top 10 Link Predictions basierend auf Adamic-Adar:")
for u, v, score in aa_scores[:10]:
    print(f"{u} - {v}: Adamic-Adar = {score:.4f}")

print(G)

Top 10 Link Predictions basierend auf Adamic-Adar:
JAR JAR - NUTE GUNRAY: Adamic-Adar = 2.3052
OBI-WAN - RABE: Adamic-Adar = 2.3002
EMPEROR - OBI-WAN: Adamic-Adar = 1.9679
ANAKIN - SIO BIBBLE: Adamic-Adar = 1.8439
SIO BIBBLE - BOSS NASS: Adamic-Adar = 1.8439
RIC OLIE - PADME: Adamic-Adar = 1.8168
RIC OLIE - BOSS NASS: Adamic-Adar = 1.8168
JABBA - OBI-WAN: Adamic-Adar = 1.7987
JABBA - KITSTER: Adamic-Adar = 1.7987
SEBULBA - KITSTER: Adamic-Adar = 1.7987
Graph with 38 nodes and 135 edges

# Welcher NOde kommt wie oft vor in den top 10
top_nodes = [u for u, _, _ in aa_scores[:10]]
top_nodes += [v for _, v, _ in aa_scores[:10]]
top_nodes = dict.fromkeys(top_nodes, 0)

for u, v, _ in aa_scores[:10]:
    top_nodes[u] += 1
    top_nodes[v] += 1

print("Top 10 Nodes in Link Predictions:")

for node, count in sorted(top_nodes.items(), key=lambda x: x[1], reverse=True):
    print(f"{node}: {count}")

Top 10 Nodes in Link Predictions:
OBI-WAN: 3
SIO BIBBLE: 2
RIC OLIE: 2
JABBA: 2
BOSS NASS: 2
KITSTER: 2
JAR JAR: 1
EMPEROR: 1
ANAKIN: 1
SEBULBA: 1
NUTE GUNRAY: 1
RABE: 1
PADME: 1

Wie bei Resource Allocation zeigt auch die Ademic Adar Metrik drei link Predictions für Obi-Wan. Allerdings ist hier der Charakter "Tey How" nicht mehr vertreten. Dies ist erstaunlich, da die Metrik fast gleich funktioniert wie die Resource Allocation.

pos = nx.spring_layout(G)
plt.figure(figsize=(12, 6))

# Netzwerk mit Adamic-Adar Link Prediction
plt.subplot(121)  
nx.draw(G, pos, with_labels=True, font_size=8, node_size=400)
nx.draw_networkx_edges(G, pos, edgelist=[(u, v) for u, v, _ in aa_scores[:10]], edge_color='r', width=2)
plt.title("Star Wars Episode 1 Interaction Network\nwith Adamic-Adar Link Prediction")

# Netzwerk ohne Link Prediction
plt.subplot(122)  
nx.draw(G, pos, with_labels=True, font_size=8, node_size=400)
plt.title("Star Wars Episode 1 Interaction Network")

# plot anzeigen
plt.tight_layout() 
plt.show()

5.5 Sind Links zustande gekommen?

Um die Linkpredictions noch zu pfüfen, schauen wir uns im Datensatz mit allen 7 Filmen an, ob eine von den Predictions wahr geworden ist, respektive ob eine der vorgeschlagenen Connections in einem späteren Film tatsächlich zustande gekommen ist.

Dazu verwenden wir von allen Metriken die jeweils beste Vorhersagen.

Höchste Wahrscheinlichkeit pro Link Prediction:

Common Neighbours: NUTE GUNRAY - JAR JAR: gemeinsame Nachbarn = 5

Jaccard Coefficient: RIC OLIE - BOSS NASS: Jaccard = 0.6250

Resource Allocation: OBI-WAN - RABE: RA = 0.5855

Ademic Adar: NUTE GUNRAY - JAR JAR: Adamic-Adar = 2.3159 - gleiche wie bei Common Neighbours

with open('data/starwars-full-interactions-allCharacters-merged.json') as f:
    data_interactions = json.load(f)

G = nx.Graph()

# connections für Links hinzufügen
for node in data_interactions['nodes']:
    G.add_node(node['name'])

for link in data_interactions['links']:
    src_id = link['source']
    tgt_id = link['target']
    source_name = data_interactions['nodes'][src_id]['name']
    target_name = data_interactions['nodes'][tgt_id]['name']
    G.add_edge(source_name, target_name)

# checken, ob es verbindungen gibt
print(f"Connection between NUTE GUNRAY and JAR JAR: {G.has_edge('NUTE GUNRAY', 'JAR JAR')}")
print(f"Connection between RIC OLIE and BOSS  NASS: {G.has_edge('RIC OLIE', 'BOSS NASS')}")
print(f"Connection between NUTE OBI-WAN and RABE: {G.has_edge('OBI-WAN', 'RABE')}")
print(G)

Connection between NUTE GUNRAY and JAR JAR: False
Connection between RIC OLIE and BOSS  NASS: False
Connection between NUTE OBI-WAN and RABE: False
Graph with 111 nodes and 444 edges

Anscheinend, sind diese Link-predictions nicht ganz so gut gewesen, denn aus den drei besten Predictions ist keine wirklich so entstanden.

Um zu prüfen, ob es sonst Links gibt, welche in den späteren Filmen entstanden sind, printen wir noch ein paar Connections mehr, welche von den Link-Prediction Methoden vorhergesagt wurden.

print(f"Connection between OBI-WAN and EMPEROR: {G.has_edge('OBI-WAN', 'EMPEROR')}")
print(f"Connection between ANAKIN and SIO BIBBLE: {G.has_edge('ANAKIN', 'SIO BIBBLE')}")
print(f"Connection between JABBA and KITSTER: {G.has_edge('JABBA', 'KITSTER')}")
print(f"Connection between RIC OLIE and PADME: {G.has_edge('RIC OLIE', 'PADME')}")
print(f"Connection between OBI-WAN and JABBA: {G.has_edge('OBI-WAN', 'JABBA')}")

Connection between OBI-WAN and EMPEROR: True
Connection between ANAKIN and SIO BIBBLE: False
Connection between JABBA and KITSTER: False
Connection between RIC OLIE and PADME: False
Connection between OBI-WAN and JABBA: False

Die einzige tatsächliche Interaktion, welche wir feststellen konnten ist die zwischen Obi-Wan und dem Emperor.

5.6 Link-Predictions auf mentions mit Common Neighbours

Nun führen wir die Link-predictions auch noch auf die Datensätze mit den Mentions durch um zu sehen, wie die Erwähnungen vorhergesagt werden und ob es nennenswerte Unterschiede gibt zu den Daten mit den Interaktionen.

with open('data/starwars-episode-1-mentions.json') as f:
    data_interactions = json.load(f)

# Graph erstellen
G = nx.Graph()

for node in data_interactions['nodes']:
    G.add_node(node['name'])

for link in data_interactions['links']:
    src_id = link['source']
    tgt_id = link['target']
    source_name = data_interactions['nodes'][src_id]['name']
    target_name = data_interactions['nodes'][tgt_id]['name']
    G.add_edge(source_name, target_name)

print(G)

Graph with 38 nodes and 244 edges

Hier ist bereits zu sehen, dass dieses Netzwerk zwar auch 38 Nodes hat, aber dafür viel mehr edges, als das Netzwerk der Interaktionen. Das ist durchaus nachvollziehbar, da hier auch Links zu Charakteren dabei sind, welche "nur" erwähnt wurden und keine tatsächliche Interaktion hatten. Bei dem Netzwerk der Interaktionen waren es "nur" jeweils 135 Edges, wobei es hier schon 244 sind.

# Link-Prediction mit Common Neighbours
potential_links = []
nodes = list(G.nodes())
n = len(nodes)

for i in range(n):
    for j in range(i+1, n):
        u = nodes[i]
        v = nodes[j]
        if not G.has_edge(u, v):
            cn_count = len(list(nx.common_neighbors(G, u, v)))
            if cn_count > 0:
                potential_links.append((u, v, cn_count))

potential_links.sort(key=lambda x: x[2], reverse=True)

print("Top 10 Link Predictions basierend auf Common Neighbours mit Namen:")
for u, v, score in potential_links[:10]:
    print(f"{u} - {v}: gemeinsame Nachbarn = {score}")

Top 10 Link Predictions basierend auf Common Neighbours mit Namen:
NUTE GUNRAY - ANAKIN: gemeinsame Nachbarn = 11
YODA - R2-D2: gemeinsame Nachbarn = 11
RUNE - ANAKIN: gemeinsame Nachbarn = 11
CAPTAIN PANAKA - GENERAL CEEL: gemeinsame Nachbarn = 11
SIO BIBBLE - DARTH MAUL: gemeinsame Nachbarn = 11
PADME - GENERAL CEEL: gemeinsame Nachbarn = 11
NUTE GUNRAY - BOSS NASS: gemeinsame Nachbarn = 10
NUTE GUNRAY - R2-D2: gemeinsame Nachbarn = 10
RUNE - BOSS NASS: gemeinsame Nachbarn = 10
RUNE - R2-D2: gemeinsame Nachbarn = 10

Im Gegensatz zu dem Netzwerk mit den Interaktionen, gibt es hier mehr Common Neighbours. In der Link-prediction der Interaktionen gab es für die Top 10 Predictions nur fünf Common Neighbours, wobei es hier bei den meisten schon 11 Common Neighbours sind.

# Welcher NOde kommt wie oft vor in den top 10
top_nodes = [u for u, _, _ in potential_links[:10]]
top_nodes += [v for _, v, _ in potential_links[:10]]
top_nodes = dict.fromkeys(top_nodes, 0)

for u, v, _ in potential_links[:10]:
    top_nodes[u] += 1
    top_nodes[v] += 1

print("Top 10 Nodes in Link Predictions:")

for node, count in sorted(top_nodes.items(), key=lambda x: x[1], reverse=True):
    print(f"{node}: {count}")

Top 10 Nodes in Link Predictions:
NUTE GUNRAY: 3
RUNE: 3
R2-D2: 3
ANAKIN: 2
GENERAL CEEL: 2
BOSS NASS: 2
YODA: 1
CAPTAIN PANAKA: 1
SIO BIBBLE: 1
PADME: 1
DARTH MAUL: 1

# Positionen der Knoten berechnen
pos = nx.spring_layout(G)

# Abmessungen für den Plot
plt.figure(figsize=(12, 6))

# Netzwerk mit Link Prediction (Common Neighbours)
plt.subplot(121) 
nx.draw(G, pos, with_labels=True, font_size=8, node_size=400)
nx.draw_networkx_edges(G, pos, edgelist=potential_links[:10], edge_color='r', width=2)
plt.title("Star Wars Episode 1 Mentions Network\nwith Common Neighbours")

# Netzwerk ohne Link Prediction
plt.subplot(122)
nx.draw(G, pos, with_labels=True, font_size=8, node_size=400)
plt.title("Star Wars Episode 1 Mentions Network")

# plot zeigen
plt.tight_layout()
plt.show()
print(G)

Graph with 38 nodes and 244 edges

Die Plots für die Mentions Netzwerke sind schon viel unübersichtlicher als die bei den Interaktionen. Dies liegt daran, dass es hier viel mehr Edges gibt als im oberen Netzwerk.

5.7 Link-Predictions auf mentions mit Jaccard Coefficioen

with open('data/starwars-episode-1-mentions.json') as f:
    data_interactions = json.load(f)

# Erstellen des Graphen
G = nx.Graph()

for node in data_interactions['nodes']:
    G.add_node(node['name'])

for link in data_interactions['links']:
    src_id = link['source']
    tgt_id = link['target']
    source_name = data_interactions['nodes'][src_id]['name']
    target_name = data_interactions['nodes'][tgt_id]['name']
    G.add_edge(source_name, target_name)

# Jaccard-coefficient bererechnen
jaccard_scores = list(nx.jaccard_coefficient(G))

jaccard_scores.sort(key=lambda x: x[2], reverse=True)

# Top 10 ausgeben
print("Top 10 Link Predictions basierend auf Jaccard Coefficient:")
for u, v, score in jaccard_scores[:10]:
    print(f"{u} - {v}: Jaccard = {score:.4f}")

# Graph anzeigen
print(G)

Top 10 Link Predictions basierend auf Jaccard Coefficient:
FODE/BEED - C-3PO: Jaccard = 0.8182
JABBA - C-3PO: Jaccard = 0.8000
SIO BIBBLE - DARTH MAUL: Jaccard = 0.6471
RUNE - BOSS NASS: Jaccard = 0.6250
MACE WINDU - VALORUM: Jaccard = 0.6154
KI-ADI-MUNDI - BOSS NASS: Jaccard = 0.6154
CAPTAIN PANAKA - GENERAL CEEL: Jaccard = 0.6111
WALD - JABBA: Jaccard = 0.6000
WALD - C-3PO: Jaccard = 0.6000
WATTO - JABBA: Jaccard = 0.6000
Graph with 38 nodes and 244 edges

# Welcher NOde kommt wie oft vor in den top 10
top_nodes = [u for u, _, _ in jaccard_scores[:10]]
top_nodes += [v for _, v, _ in jaccard_scores[:10]]
top_nodes = dict.fromkeys(top_nodes, 0)

for u, v, _ in jaccard_scores[:10]:
    top_nodes[u] += 1
    top_nodes[v] += 1

print("Top 10 Nodes in Link Predictions:")

for node, count in sorted(top_nodes.items(), key=lambda x: x[1], reverse=True):
    print(f"{node}: {count}")

Top 10 Nodes in Link Predictions:
JABBA: 3
C-3PO: 3
WALD: 2
BOSS NASS: 2
FODE/BEED: 1
SIO BIBBLE: 1
RUNE: 1
MACE WINDU: 1
KI-ADI-MUNDI: 1
CAPTAIN PANAKA: 1
WATTO: 1
DARTH MAUL: 1
VALORUM: 1
GENERAL CEEL: 1

Mit der Jaccard Coefficient Metrik ist es interessant zu sehen, dass der Charakter Jira nicht mehr vorkommt in den Top 10 Link Predictions. Dieser war bei dem Netzwerk mit den Interaktionen sechs mal in den Top 10. Woran das genau liegt, ist allerdings schwer zu sagen.

# Positionen der Knoten berechnen
pos = nx.spring_layout(G)
 
plt.figure(figsize=(12, 6))

# Netzwerk mit Jaccard Link Prediction
plt.subplot(121)  
nx.draw(G, pos, with_labels=True, font_size=8, node_size=400)
nx.draw_networkx_edges(G, pos, edgelist=[(u, v) for u, v, _ in jaccard_scores[:10]], edge_color='r', width=2)
plt.title("Star Wars Episode 1 Mentions Network\nwith Jaccard Link Prediction")

# Netzwerk ohne Link Prediction
plt.subplot(122)  
nx.draw(G, pos, with_labels=True, font_size=8, node_size=400)
plt.title("Star Wars Episode 1 Mentions Network")

# Abbildung anzeigen
plt.tight_layout()  
plt.show()

5.8 Link-Predictions auf mentions mit Resource Allocation

with open('data/starwars-episode-1-mentions.json') as f:
    data_interactions = json.load(f)

G = nx.Graph()

# für alle links in data_interactions einen Knoten hinzufügen
for node in data_interactions['nodes']:
    G.add_node(node['name'])

for link in data_interactions['links']:
    src_id = link['source']
    tgt_id = link['target']
    source_name = data_interactions['nodes'][src_id]['name']
    target_name = data_interactions['nodes'][tgt_id]['name']
    G.add_edge(source_name, target_name)


# Resource Allocation
ra_scores = list(nx.resource_allocation_index(G))
ra_scores.sort(key=lambda x: x[2], reverse=True)

print("Top 10 Link Predictions basierend auf Resource Allocation:")
for u, v, score in ra_scores[:10]:
    print(f"{u} - {v}: RA = {score:.4f}")
print(G)

Top 10 Link Predictions basierend auf Resource Allocation:
RUNE - ANAKIN: RA = 0.6010
ANAKIN - NUTE GUNRAY: RA = 0.6010
CAPTAIN PANAKA - GENERAL CEEL: RA = 0.6003
PADME - GENERAL CEEL: RA = 0.6003
SIO BIBBLE - DARTH MAUL: RA = 0.5597
R2-D2 - YODA: RA = 0.5525
R2-D2 - NUTE GUNRAY: RA = 0.5385
R2-D2 - RUNE: RA = 0.5385
RUNE - BOSS NASS: RA = 0.5176
NUTE GUNRAY - BOSS NASS: RA = 0.5176
Graph with 38 nodes and 244 edges

# Welcher NOde kommt wie oft vor in den top 10
top_nodes = [u for u, _, _ in ra_scores[:10]]
top_nodes += [v for _, v, _ in ra_scores[:10]]
top_nodes = dict.fromkeys(top_nodes, 0)

for u, v, _ in ra_scores[:10]:
    top_nodes[u] += 1
    top_nodes[v] += 1

print("Top 10 Nodes in Link Predictions:")

for node, count in sorted(top_nodes.items(), key=lambda x: x[1], reverse=True):
    print(f"{node}: {count}")

Top 10 Nodes in Link Predictions:
RUNE: 3
R2-D2: 3
NUTE GUNRAY: 3
ANAKIN: 2
GENERAL CEEL: 2
BOSS NASS: 2
CAPTAIN PANAKA: 1
PADME: 1
SIO BIBBLE: 1
DARTH MAUL: 1
YODA: 1

# Positionen der Knoten berechnen
pos = nx.spring_layout(G)
plt.figure(figsize=(12, 6))

# Netzwerk mit RA Link Prediction
plt.subplot(121)  
nx.draw(G, pos, with_labels=True, font_size=8, node_size=400)
nx.draw_networkx_edges(G, pos, edgelist=[(u, v) for u, v, _ in ra_scores[:10]], edge_color='r', width=2)
plt.title("Star Wars Episode 1 Interaction Network\nwith Resource Allocation Link Prediction")

# Netzwerk ohne Link Prediction
plt.subplot(122) 
nx.draw(G, pos, with_labels=True, font_size=8, node_size=400)
plt.title("Star Wars Episode 1 Interaction Network")

# plot anzeigen
plt.tight_layout() 
plt.show()

5.9 Link-Predictions auf mentions mit Ademic Adar

with open('data/starwars-episode-1-mentions.json') as f:
    data_interactions = json.load(f)

G = nx.Graph()

for node in data_interactions['nodes']:
    G.add_node(node['name'])

for link in data_interactions['links']:
    src_id = link['source']
    tgt_id = link['target']
    source_name = data_interactions['nodes'][src_id]['name']
    target_name = data_interactions['nodes'][tgt_id]['name']
    G.add_edge(source_name, target_name)


# Adamic-Adar
aa_scores = list(nx.adamic_adar_index(G))
aa_scores.sort(key=lambda x: x[2], reverse=True)

print("Top 10 Link Predictions basierend auf Adamic-Adar:")
for u, v, score in aa_scores[:10]:
    print(f"{u} - {v}: Adamic-Adar = {score:.4f}")

print(G)

Top 10 Link Predictions basierend auf Adamic-Adar:
RUNE - ANAKIN: Adamic-Adar = 3.7620
ANAKIN - NUTE GUNRAY: Adamic-Adar = 3.7620
CAPTAIN PANAKA - GENERAL CEEL: Adamic-Adar = 3.7592
PADME - GENERAL CEEL: Adamic-Adar = 3.7592
SIO BIBBLE - DARTH MAUL: Adamic-Adar = 3.6693
R2-D2 - YODA: Adamic-Adar = 3.6586
R2-D2 - NUTE GUNRAY: Adamic-Adar = 3.4013
R2-D2 - RUNE: Adamic-Adar = 3.4013
RUNE - BOSS NASS: Adamic-Adar = 3.3595
NUTE GUNRAY - BOSS NASS: Adamic-Adar = 3.3595
Graph with 38 nodes and 244 edges

# Welcher NOde kommt wie oft vor in den top 10
top_nodes = [u for u, _, _ in aa_scores[:10]]
top_nodes += [v for _, v, _ in aa_scores[:10]]
top_nodes = dict.fromkeys(top_nodes, 0)

for u, v, _ in aa_scores[:10]:
    top_nodes[u] += 1
    top_nodes[v] += 1

print("Top 10 Nodes in Link Predictions:")

for node, count in sorted(top_nodes.items(), key=lambda x: x[1], reverse=True):
    print(f"{node}: {count}")

Top 10 Nodes in Link Predictions:
RUNE: 3
R2-D2: 3
NUTE GUNRAY: 3
ANAKIN: 2
GENERAL CEEL: 2
BOSS NASS: 2
CAPTAIN PANAKA: 1
PADME: 1
SIO BIBBLE: 1
DARTH MAUL: 1
YODA: 1

pos = nx.spring_layout(G)
plt.figure(figsize=(12, 6))

# Netzwerk mit Adamic-Adar Link Prediction
plt.subplot(121)  
nx.draw(G, pos, with_labels=True, font_size=8, node_size=400)
nx.draw_networkx_edges(G, pos, edgelist=[(u, v) for u, v, _ in aa_scores[:10]], edge_color='r', width=2)
plt.title("Star Wars Episode 1 Mentions Network\nwith Adamic-Adar Link Prediction")

# Netzwerk ohne Link Prediction
plt.subplot(122)  
nx.draw(G, pos, with_labels=True, font_size=8, node_size=400)
plt.title("Star Wars Episode 1 Mentions Network")

# plot anzeigen
plt.tight_layout() 
plt.show()

5.10 Link-Prediction überprüfen

Die jeweils höchsten Scores und somit die Connections, welche wir überprüfen wollen sind die folgenden:

NUTE GUNRAY - ANAKIN: gemeinsame Nachbarn = 11

C-3PO - FODE/BEED: Jaccard = 0.8182

ANAKIN - RUNE: RA = 0.6010

ANAKIN - RUNE: Adamic-Adar = 3.7620

with open('data/starwars-full-mentions.json') as f:
    data_interactions = json.load(f)

G = nx.Graph()

# connections für Links hinzufügen
for node in data_interactions['nodes']:
    G.add_node(node['name'])

for link in data_interactions['links']:
    src_id = link['source']
    tgt_id = link['target']
    source_name = data_interactions['nodes'][src_id]['name']
    target_name = data_interactions['nodes'][tgt_id]['name']
    G.add_edge(source_name, target_name)

# checken, ob es verbindungen gibt
print(f"Connection between NUTE GUNRAY and ANAKIN: {G.has_edge('NUTE GUNRAY', 'ANAKIN')}")
print(f"Connection between C-3PO and FODE/BEED: {G.has_edge('C-3PO', 'FODE/BEED')}")
print(f"Connection between ANAKIN and RUNE: {G.has_edge('ANAKIN', 'RUNE')}")
print(G)

Connection between NUTE GUNRAY and ANAKIN: True
Connection between C-3PO and FODE/BEED: False
Connection between ANAKIN and RUNE: True
Graph with 113 nodes and 817 edges

Zwei von den drei geprüften Connections, welche durch die Link-prediction vorhergesagt wurden, sind tätsachlich so entstanden. Dies ist schon mehr als beim Netzwerk mit den Interaktionen.

Auch hier testen wir noch ein paar andere Link-Predictions und sehen uns an, ob es über den Verlauf der sieben Filme tatsächlich zu den Mentions gekommen ist.

print(f"Connection between OBI-WAN and EMPEROR: {G.has_edge('GENERAL CEEL', 'CAPTAIN PANAKA')}")
print(f"Connection between ANAKIN and SIO BIBBLE: {G.has_edge('SIO BIBBLE', 'DARTH MAUL')}")
print(f"Connection between JABBA and KITSTER: {G.has_edge('YODA', 'R2-D2')}")
print(f"Connection between RIC OLIE and PADME: {G.has_edge('RUNE', 'R2-D2')}")
print(f"Connection between OBI-WAN and JABBA: {G.has_edge('BOSS NASS', 'RUNE')}")

Connection between OBI-WAN and EMPEROR: False
Connection between ANAKIN and SIO BIBBLE: False
Connection between JABBA and KITSTER: True
Connection between RIC OLIE and PADME: False
Connection between OBI-WAN and JABBA: False

Hier sehen wir, dass es nur bei einem von fünf vorhergesagten Links tatsächlich zu einer Erwähnung (Mention) gekommen ist.

5.11 Fazit der Link Prediction und Empfehlung an den Imperator

Es ist interessant zu sehen, dass bei den Interaktionen und auch bei den Mentions jeweils nur sehr wenige der vorhergesagten Connections wirklich zu stande gekommen sind. Dies ist wohl ein Exampel dafür, dass eine Link-prediction in der Theorie zwar Sinn ergibt, in der Praxis allerdings recht schwierig vorherzusagen ist.

Dem Imperator würden wir die Folgenden Charaktere empfehlen zu verbünden:

Nute Gunray und Jar Jar, da diese den höchsten Wert haben bei Common Neighbours und bei Ademic Adar

Ric Olie und Boss Nass, da diese den höchsten Wert haben beim Jaccard Coefficient.

Obi-Wan und Rabe, da diese den höchsten Wert haben bei Resource Allocation.

Die Empfehlung basiert auf den Link-Predictions des Netzwerkes mit den Interaktionen und nicht dem mit den Mentions, da dem Imperator der Informationsfluss wichtig ist.

6 Ausblick

Es gibt noch weitere Möglichkeiten um vortgeschrittenere oder komplexere Netzwerkanalysen durchzuführen. Als nächste Schritte für die Bekämpfung des Imperators gäbe es beispielsweise folgende Techniken.

6.1 Weitere Metriken (Eigenvektorzentralität)

Mit der Eigenvektor-Zentralität lassen sich zentrale Knoten eines Netzwerks identifizieren, indem nicht nur ihre eigene Wichtigkeit, sondern auch die Bedeutung ihrer Nachbarn in die Berechnung einbezogen wird. Je höher die Eigenvektor-Zentralität der Nachbarn eines Knotens, desto grösser ist auch die Eigenvektor-Zentralität dieses Knotens.

In Bezug auf die analysierten Datensätze bedeutet dies, dass Knoten identifiziert werden können, die nicht unbedingt selbst die wichtigsten sind, jedoch in direkter Nachbarschaft zu den zentralen Knoten stehen. Der Imperator könnte daher eine alternative Strategie verfolgen: Anstatt die zentralsten Knoten direkt ins Visier zu nehmen, könnte er sich auf deren Nachbarn konzentrieren. Diese könnten als Schlüsselakteure oder Manipulatoren genutzt werden, um seine Ziele indirekt zu erreichen.

6.2 Diffusion

Diffusion bezeichnet in der sozialen Netzwerkanalyse den Prozess der Informations- oder Wissensverbreitung über Beziehungen zwischen Individuen oder Gruppen. Dadurch können sich neues Wissen, Verhaltensweisen oder Technologien schnell und weitreichend in einer Gesellschaft oder Organisation durchsetzen.

Für unsere Minichallenge wäre dies nützlich um beispielsweise die Charaktere anhand ihrer Interaktionen (z. B. gemeinsame Szenen, direkte Gespräche, Weitergabe von Informationen) als Knoten in einem Netzwerk zu betrachten und zu untersuchen, wie schnell bestimmte Informationen („Luke ist Darth Vaders Sohn“) oder Überzeugungen („die Macht nutzen“) in diesem Gefüge weitergegeben werden. Dabei könnten zentrale Figuren wie Obi-Wan Kenobi oder Yoda als „Schlüsselvermittler“ fungieren, weil sie in der Story als "Lehrer" entscheidend zum Erlernen der Macht beitragen. Die Analyse würde zeigen, welche Charaktere besonders einflussreich sind und in welchen Untergruppen Ideen oder Informationen nur langsam oder gar nicht ankommen. Insgesamt könnten so Mechanismen sichtbar gemacht werden, wie zentrale Handlungsstränge, Ideologien oder Geheimnisse innerhalb der Star-Wars-Saga von Figur zu Figur „diffundieren“.

6.3 Graphlets

Man könnte des weiteren noch versuchen Graphlets mit in die Minichallenge einzubeziehen. Graphlets sind kleine, verbundene Subgraphen in einem typischen Umfang von 2 bis 5 Knoten. Sie können dazu verwendet werden, strukturelle Ähnlichkeit von Knoten zu untersuchen. So können beispielsweise Gruppen von Knoten in einem Netzwerk ausndig gemacht werden, welche sich zwar an komplett unterschiedlichen Positionen befinden, aber ähnliche lokale Verbindungsmuster aufweisen.

Beispielsweise könnte man über die Häufigkeit verschiedener Graphlet types hinweg verschiedene Netzwerkzustände (z. B. unterschiedliche Filme der Sage, also beispielsweise Film 1 und Film 4) vergleichen. So wäre ersichtlich, ob sich die Beziehungen in bestimmten Episoden besonders stark um einen oder wenige Knoten zentriert oder ob es viele eng vernetzte Untergruppen gibt. Durch zählen bestimmter Graphlets liesse sich eventuell auch erkennen, an welchen Stellen im Netzwerk Information besonders schnell weitergegeben werden könnte oder vieleicht "hängen bleiben". Somit könnten wir weitere Einblicke erhalten, welche Charaktere oder Gruppen für die Verbreitung von Desinformation durch den Imperator entscheidend sind.

7 Fazit

Die Minichallenge für das Modul SAN hat uns geholfen, die gelernte Theorie von der Zwischenprüfung mit praktischer Anwendung besser zu verstehen. Es war für uns interessant zu sehen, wie die verschiedenen Methoden und Ansätze der Sozialen Netzwerkanalyse praktisch umgesetzt werden können. Auch war es interessant zu sehen, dass man die Taktik des Imperators gestalten kann, je nach dem wie die Werte der Aktor Zentralität aussehen, ob er jemanden auf seine Seite bringen soll, oder einen Charakter Eliminieren.

Wir hoffen, dass wir dem Universum mit der Minichallenge helfen konnten und somit bald wieder eine Ordnung in der Galaxie herrscht.

Möge die Macht mit dir sein!